package com.dai.code;

import com.dai.common.NodeWithRandomNext;

import java.util.HashMap;
import java.util.Map;

/**
 * 带随机节点的链表深克隆
 *
 * @author daijiyong
 */
public class DeepCloneLinkedList {
    public static void main(String[] args) {
        NodeWithRandomNext list = new NodeWithRandomNext(1);
        NodeWithRandomNext temp = list;
        NodeWithRandomNext cross = null;
        for (int i = 2; i < 10; i++) {
            temp.next = new NodeWithRandomNext(i);
            temp = temp.next;
            if (i == 5) {
                cross = temp;
                cross.random = cross;
            }
            if (i == 8) {
                temp.random = cross;
            }
        }

        NodeWithRandomNext clone1 = deepClone1(list);
        NodeWithRandomNext clone2 = deepClone2(list);
        System.out.printf("深克隆带随机指针的链表1%s：%s\n", list == clone1 ? "失败" : "成功", clone1);
        System.out.printf("深克隆带随机指针的链表2%s：%s\n", list == clone2 ? "失败" : "成功", clone2);
    }

    public static NodeWithRandomNext deepClone1(NodeWithRandomNext list) {
        if (list == null) {
            return null;
        }

        NodeWithRandomNext pointer = new NodeWithRandomNext();
        NodeWithRandomNext temp = list;
        Map<NodeWithRandomNext, NodeWithRandomNext> nodeMap = new HashMap<>();
        // 先遍历所有节点，并复制一份
        while (temp != null) {
            nodeMap.putIfAbsent(temp, new NodeWithRandomNext(temp.value));
            temp = temp.next;
        }
        temp = nodeMap.get(list);
        pointer.next = temp;
        // 再次遍历所有节点，并梳理前后和随机关系
        while (temp != null) {
            temp.next = nodeMap.get(list.next);
            temp.random = nodeMap.get(list.random);
            list = list.next;
            temp = temp.next;
        }

        return pointer.next;
    }

    public static NodeWithRandomNext deepClone2(NodeWithRandomNext list) {
        if (list == null) {
            return null;
        }
        // 复制所有节点
        copy(list);
        // 挂接所有随机节点
        copyRandom(list);
        // 拆分出复制后的节点，并返回
        return split(list);
    }

    private static NodeWithRandomNext split(NodeWithRandomNext list) {
        NodeWithRandomNext result = list.next;
        NodeWithRandomNext temp = list.next;
        while (list != null && list.next != null) {
            list.next = list.next.next;
            list = list.next;
            if (temp != null && temp.next != null) {
                temp.next = temp.next.next;
                temp = temp.next;
            }
        }
        return result;
    }

    private static void copyRandom(NodeWithRandomNext list) {
        NodeWithRandomNext node = list;
        while (node != null && node.next != null) {
            if (node.random != null) {
                node.next.random = node.random.next;
            }
            node = node.next.next;
        }
    }

    private static void copy(NodeWithRandomNext list) {
        NodeWithRandomNext node = list;
        while (node != null) {
            NodeWithRandomNext copy = new NodeWithRandomNext(node.value);
            copy.next = node.next;
            node.next = copy;
            node = copy.next;
        }
    }

}
